package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 652. 寻找重复的子树
 *
 * @Author liw
 * @Date 2021/5/12 14:18
 * @Version 1.0
 */
public class FindDuplicateSubtrees {


    public static void main(String[] args) {
        FindDuplicateSubtrees test = new FindDuplicateSubtrees();
        // [0,0,0,0,null,null,0,null,null,null,0]  [[0],[0,null,0]]  [[0]]

    }

    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> list = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        find(root);
        return list;
    }

    public StringBuilder find(TreeNode node) {
        if (node == null) {
            return new StringBuilder("n");
        }
        StringBuilder l = find(node.left);
        StringBuilder r = find(node.right);
        l.append('l');
        l.append(r);
        l.append('r');
        l.append(node.val);
        String key = l.toString();
        Integer value = map.get(key);
        if (value == null) {
            map.put(key, 1);
        } else {
            if (value == 1) {
                list.add(node);
            }
            map.put(key, value + 1);
        }
        return l;
    }

}
